package com.xjj.hash;

import java.util.HashMap;
import java.util.Map;

// TODO 优化双向链表的实现
public class M0146LruCache {

    private Map<Integer, Node> map = new HashMap<>();

    private Node head = null;

    private Node tail = null;

    private int capacity;

    private int size = 0;

    public M0146LruCache(int capacity) {
        this.capacity = capacity;
        head = new Node(0, 0);
        tail = head;
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            // 获取也要更新数据
            insertHead(key, remove(key));
            return map.get(key).value;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        // 存在走更新,先链表删除再添加
        if (map.containsKey(key)) {
            Node node = remove(key);
            node.value = value;
            insertHead(key, node);
        } else {
            Node node = new Node(key, value);
            // 要判断capacity
            if (size < capacity) {
                // 直接添加
                insertHead(key, node);
            } else {
                remove(tail.pre.key);
                insertHead(key, node);
            }
        }
    }

    private void insertHead(int key, Node node) {
        map.put(key, node);
        // 只做插入头的操作,其他操作在其他方法已经执行
        node.next = head.next;
        node.pre = head;

        node.next.pre = node;
        node.pre.next = node;
        size++;
    }

    private Node remove(int key) {
        // System.out.println("remove " + key);
        Node node = map.remove(key);
        if (node == null) {
            return node;
        }
        node.next.pre = node.pre;
        node.pre.next = node.next;
        size--;
        return node;
    }

    public class Node {

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public Node pre;

        public Node next;

        public int key;

        public int value;

    }

}
